package com.xpchenfrank.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 慧博云通面试题
 *
 * @author xpchen
 * @time 2019\2\19 0019 1:31
 * @Description
 * @copyright Wuxi Yazuo ,Ltd.copyright 2015-2025
 */
public class CalNum {

    public static void main(String[] args) {
        Integer[] intArray = {1, 5, 2};
        int target = 110000000;

        long start=System.currentTimeMillis();
        int result = CalNum.calNum(intArray, target);
        long end=System.currentTimeMillis();
        //System.out.println("result size is " + result);
        System.out.println("方案一当前程序耗时："+ (end-start) +"ms");


        start=System.currentTimeMillis();
        result = CalNum.calNumMod(intArray, target);
        end=System.currentTimeMillis();
        //System.out.println("result size is " + result);
        System.out.println("方案二当前程序耗时："+ (end-start) +"ms");

    }


    public static int calNum(Integer[] intArray, int target) {

        Arrays.sort(intArray, new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                if(o1 != null && o2 != null) {
                    return o2 - o1;
                } else {
                    return 0;
                }
            }
        });

        for (int i : intArray) {
            System.out.println("i is " + i);
        }
        int tempTarget = target;
        List<Integer> resultList = new ArrayList<Integer>();
        while(tempTarget > 0) {
            for (Integer integer : intArray) {
                int minusVal = tempTarget - integer;
                if(minusVal >= 0) {
                    tempTarget = minusVal;
                    resultList.add(integer);
                    break;
                }
            }
        }

//        for (Integer integer : resultList) {
//            System.out.println("result is " + integer);
//        }
        return resultList.size();

    }

    public static int calNumMod(Integer[] intArray, int target) {

        Arrays.sort(intArray, new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                if(o1 != null && o2 != null) {
                    return o2 - o1;
                } else {
                    return 0;
                }
            }
        });

        int tempTarget = target;
        List<Integer> resultList = new ArrayList<Integer>();
        while(tempTarget > 0) {
            for (Integer integer : intArray) {
                if(integer != 0) {
                    int modVal = tempTarget % integer;
                    if(modVal >= 0) {
                        int times = tempTarget / integer;
                        if(times > 0) {
                            tempTarget = modVal;
                            for(int i=0; i<times; i++) {
                                resultList.add(integer);
                            }
                            break;
                        }
                    }
                }
            }
        }

//        for (Integer integer : resultList) {
//            System.out.println("result is " + integer);
//        }
        return resultList.size();

    }

}
